#include "myTree.h"
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void TreeNode::printNode()
{
    cout << this->data;
}

TreeNode::TreeNode(char c, TreeNode *l, TreeNode *r, NodeTag p, NodeTag a)
{
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = c;
    newNode->leftChild = l;
    newNode->rightChild = r;
    p = Link;
    a = Link;
}

TreeNode::TreeNode(char c, TreeNode *l, TreeNode *r)
{
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = c;
    newNode->leftChild = l;
    newNode->rightChild = r;
}

TreeNode::~TreeNode()
{
    delete leftChild;
    delete rightChild;
}

MyTree::MyTree()
{
    root = nullptr;
    isThread = 0;
}

MyTree::MyTree(const char preOrder[])
{
    root = nullptr;
    int i = 0;
    this->root = CreateBiTree(preOrder, i);
    isThread = 0;
}

TreeNode *MyTree::CreateBiTree(const char pre[], int &i)
{
    // cout << i << " " << pre[i] << endl;
    if (pre[i] == '@')
    {
        i++;
        return NULL;
    }
    // cout << " not @\n";
    TreeNode *newnode = (TreeNode *)malloc(sizeof(TreeNode));
    newnode->data = pre[i];
    i++;
    // cout << " newnode->data" << newnode->data;
    newnode->leftChild = CreateBiTree(pre, i);
    newnode->rightChild = CreateBiTree(pre, i);
    return newnode;
}

MyTree::MyTree(const MyTree &T)
{
    root = CopyTree(T.root);
    isThread = 0;
}

TreeNode *MyTree::CopyTree(TreeNode *root) // 复制树
{
    if (root == NULL)
    {
        return NULL;
    }
    TreeNode *newnode = (TreeNode *)malloc(sizeof(TreeNode));
    newnode->data = root->data;
    newnode->leftChild = CopyTree(root->leftChild);
    newnode->rightChild = CopyTree(root->rightChild);
    return newnode;
}

void MyTree::preOrderTraverse() // 前序遍历
{
    preOrder(this->root);
}

void MyTree::preOrder(TreeNode *root)
{
    if (root == NULL)
    {
        return;
    }
    cout << root->data;
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}

void MyTree::inOrderTraverse() // 中序遍历
{
    inOrderTraverse(this->root);
}

void MyTree::inOrderTraverse(TreeNode *root)
{
    if (root == NULL)
    {
        return;
    }
    if (!isThread || root->lTag == Link)
        inOrderTraverse(root->leftChild);
    cout << root->data;
    if (!isThread || root->lTag == Link)
        inOrderTraverse(root->rightChild);
}

void MyTree::postOrderTraverse()
{
    postOrderTraverse(this->root);
}

void MyTree::postOrderTraverse(TreeNode *root) // 后序遍历
{
    if (root == NULL)
    {
        return;
    }
    postOrderTraverse(root->leftChild);
    postOrderTraverse(root->rightChild);
    cout << root->data;
}

int MyTree::countLeaf()
{
    return countLeaf(this->root);
}

int MyTree::countLeaf(TreeNode *root)
{
    if (root == NULL)
    {
        return 0;
    }
    else if (root->leftChild == NULL && root->rightChild == NULL)
    {
        return 1;
    }
    else
        return countLeaf(root->leftChild) + countLeaf(root->rightChild);
}

int MyTree::countHeight()
{
    return countHeight(this->root);
}

int MyTree::countHeight(TreeNode *root)
{
    if (root == NULL)
    {
        return 0;
    }
    int m = countHeight(root->leftChild);
    int n = countHeight(root->rightChild);
    return (m > n) ? m + 1 : n + 1;
}

bool MyTree::isThreadedTree()
{
    if (this->isThread)
    {
        return true;
    }
    return false;
}

bool MyTree::inOrderThreading()
{ // 线索化
    isThread = true;
    TreeNode *preNode = nullptr;
    Threading(root, preNode);
    return true;
}
void MyTree::Threading(TreeNode *p, TreeNode *&preNode)
{
    if (p != NULL)
    {
        Threading(p->leftChild, preNode);
        if (p->leftChild == NULL)
        {
            p->leftChild = preNode;
            p->lTag = Thread;
        }
        if (preNode != NULL && preNode->rightChild == NULL)
        {
            preNode->rightChild = p;
            preNode->rTag = Thread;
        }
        preNode = p;
        Threading(p->rightChild, preNode);
    }
}
TreeNode &MyTree::locateNode(const char &x)
{ // 结点定位
    TreeNode *result = nullptr;
    preOrderLocate(root, x, result);
    return *result;
}
void MyTree::preOrderLocate(TreeNode *P, const char &x, TreeNode *&result)
{
    if (P != NULL && result == NULL)
    {
        if (P->data == x)
        {
            result = P;
        }
        else
        {
            if (!isThread || P->lTag == Link)
                preOrderLocate(P->leftChild, x, result);
            if (!isThread || P->rTag == Link)
                preOrderLocate(P->rightChild, x, result);
        }
    }
}

TreeNode &MyTree::preNode(const TreeNode &node)
{ // 获取前驱结点
    TreeNode *p = (&node)->leftChild;
    if (p == NULL)
    {
        // 如果没有前驱
    }
    else if ((&node)->lTag == Thread)
    {
        return *p;
    }
    else
    {
        while (p->rTag == Link)
            p = p->rightChild;
        return *p;
    }
}
TreeNode &MyTree::nextNode(const TreeNode &node)
{ // 获取后继结点
    TreeNode *p = (&node)->rightChild;
    if (p == NULL)
    {
        // 如果没有前驱
    }
    else if ((&node)->rTag == Thread)
    {
        return *p;
    }
    else
    {
        while (p->lTag == Link)
            p = p->leftChild;
        return *p;
    }
}

void HuffmanTree::CreateHuffmanTree(const int weights[], int n)
{
    numNodes = 2 * n - 1;
    mytree = new HuffmanNode[numNodes];

    for (int i = 0; i < n; i++)
    {
        mytree[i].weight = weights[i];
    }

    // 构建Huffman树
    for (int i = n; i < numNodes; i++)
    {
        int min1 = -1, min2 = -1;
        for (int j = 0; j < i; j++)
        {
            if (mytree[j].parent == -1)
            {
                if (min1 == -1 || mytree[j].weight < mytree[min1].weight)
                {
                    min2 = min1;
                    min1 = j;
                }
                else if (min2 == -1 || mytree[j].weight < mytree[min2].weight)
                {
                    min2 = j;
                }
            }
        }
        // 合并两个最小节点
        mytree[i].weight = mytree[min1].weight + mytree[min2].weight;
        mytree[i].leftChild = min1;
        mytree[i].rightChild = min2;
        mytree[min1].parent = i;
        mytree[min2].parent = i;
        root = i;
    }
}

void HuffmanTree::GenerateCodes(int n)
{
    for (int i = 0; i < n; i++)
    {
        int current = i;
        int parent = mytree[i].parent;
        string code = "";

        // 回溯从叶子节点到根节点生成编码
        while (parent != -1)
        {
            if (mytree[parent].leftChild == current)
                code = "0" + code;
            else
                code = "1" + code;
            current = parent;
            parent = mytree[current].parent;
        }
        mytree[i].code = code; // 将编码赋值给叶子节点
    }
}

HuffmanTree::HuffmanTree(const int &n, const int weight[])
{
    CreateHuffmanTree(weight, n);
    GenerateCodes(n);
}

void HuffmanTree::printHuffmanCodes()
{
    // 将节点按照权重排序
    vector<pair<int, string>> codes;
    for (int i = 0; i < numNodes / 2 + 1; i++)
    {
        codes.push_back({mytree[i].weight, mytree[i].code});
    }
    sort(codes.rbegin(), codes.rend());

    // 输出格式：节点值：编码
    for (auto &code : codes)
    {
        cout << code.first << ":" << code.second << endl;
    }
}

HuffmanTree::~HuffmanTree()
{
    delete[] mytree;
}